package offer.offer02;

import java.util.HashMap;
import java.util.Map;

/**
 * 二叉搜索树的中序遍历就是递增序列
 * 创建一个子函数, 会返回一个子树的最大节点和最小节点,
 * 然后把 左子树的最小节点 - 根 - 右子树的最大节点 连起来, 中序遍历递归一下就是结果
 * 我把Map中的key从String换成Integer, idea上时间变短了, LeetCode上变长了;
 *
 * 中序遍历, 然后把得到的链表连起来?或者遍历的时候就返回头和尾结点。
 * 为了返回头结点和尾结点, 需要一个新的类, 但是也可以通过全局变量来实现。
 */
public class Solution36 {
    public Node36 treeToDoublyList(Node36 root) {
        if(root == null) return null;
        long time1 = System.nanoTime();
        Node36 head = root;
        if(root.left != null){
            Map<Integer, Node36> leftMap = getMinMax(root.left);
            leftMap.get(1).right = root;
            root.left = leftMap.get(1);
            head = leftMap.get(0);
        }
        if(root.right != null){
            Map<Integer, Node36> rightMap = getMinMax(root.right);
            rightMap.get(0).left = root;
            root.right = rightMap.get(0);

            rightMap.get(1).right = head;
            head.left = rightMap.get(1);
        }else {
            root.right = head;
            head.left = root;
        }
        long time2 = System.nanoTime();
        System.out.println("用时: " + (time2 - time1));
        return head;
    }

    public Map<Integer, Node36> getMinMax(Node36 node){
        Map<Integer, Node36> retMap = new HashMap<>();
        if(node.left == null) {
            retMap.put(0, node);
        }else {
            Map<Integer, Node36> leftMap = getMinMax(node.left);
            leftMap.get(1).right = node;
            node.left = leftMap.get(1);
            retMap.put(0, leftMap.get(0));
        }
        if(node.right == null){
            retMap.put(1, node);
        }else{
            Map<Integer, Node36> rightMap = getMinMax(node.right);
            rightMap.get(0).left = node;
            node.right = rightMap.get(0);
            retMap.put(1, rightMap.get(1));
        }
        return retMap;
    }

    public static void main(String[] args) {
        Node36 root = new Node36(4, new Node36(2), new Node36(5));
        root.left.left = new Node36(1);
        root.left.right = new Node36(3);
        Node36 output = new Solution36().treeToDoublyList(root);
        for(int i = 1; i < 10; i++){
            System.out.println(output.val);
            output = output.right;
        }

    }

}
class Node36 {
    public int val;
    public Node36 left;
    public Node36 right;

    public Node36() {}

    public Node36(int _val) {
        val = _val;
    }

    public Node36(int _val,Node36 _left,Node36 _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
